package one.three.fiftyOne;

import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

public class EvaluateDeluxe {

	private static class Stack<Item> implements Iterable<Item> {
		private Node<Item> first;
		private int n;
		private boolean a = false;

		private static class Node<Item> {
			private Item item;
			private Node next;
		}

		public Stack() {
			first = null;
			n = 0;
		}

		public Stack(Stack<Item> s) {
			Item[] tmp = (Item[]) new Object[s.size()];
			Node<Item> c = s.first;
			int i = 0;
			while (c != null) {
				tmp[i] = c.item;
				i++;
				c = c.next;
			}

			for (i = tmp.length - 1; i >= 0; i--) {
				push(tmp[i]);
			}

		}

		public boolean isEmpty() {
			return first == null;
		}

		public int size() {
			return n;
		}

		public void push(Item item) {
			a = true;
			Node<Item> oldfirst = first;
			first = new Node<Item>();
			first.item = item;
			first.next = oldfirst;
			n++;
		}

		public Item pop() {

			if (isEmpty())
				throw new NoSuchElementException();
			a = true;
			Item item = first.item;
			first = first.next;
			n--;
			return item;
		}

		public Item peep() {
			if (isEmpty())
				throw new NoSuchElementException();
			Item item = first.item;
			return item;
		}

		@Override
		public String toString() {
			StringBuilder s = new StringBuilder();
			for (Item item : this) {
				s.append(item);
				s.append(" ");
			}
			return s.toString();
		}

		@Override
		public Iterator<Item> iterator() {
			return new LinkedIterator(first);
		}

		private class LinkedIterator implements Iterator<Item> {
			private Node<Item> current;

			public LinkedIterator(Node<Item> first) {
				a = false;
				current = first;
			}

			public boolean hasNext() {
				if (a) {
					throw new ConcurrentModificationException();
				}
				return current != null;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}

			@Override
			public Item next() {
				if (!hasNext())
					throw new NoSuchElementException();
				Item item = current.item;
				current = current.next;
				return item;
			}

		}

	}

	public static int cal(String[] a) {

		Stack<String> o = new Stack<String>();
		Stack<Integer> v = new Stack<Integer>();

		Map<String, Integer> p = new HashMap<String, Integer>();
		p.put("(", 0);
		p.put(")", 0);
		p.put("+", 1);
		p.put("-", 1);
		p.put("*", 2);
		p.put("/", 2);

		for (int i = 0; i < a.length; i++) {
			String e = a[i];
			if (!p.containsKey(e)) {
				v.push(Integer.parseInt(e));
				continue;
			} else {
				while (true) {
					if (o.isEmpty() || e.equals("(") || p.get(e) > p.get(o.peep())) {
						o.push(e);
						break;
					}
					String op = o.pop();
					if (op.equals("(")) {
						assert e.equals(")");
						break;
					} else {
						int v2 = v.pop();
						int v1 = v.pop();
						int r = eval(v1, v2, op);
						v.push(r);
					}
				}
			}
		}
		while (!o.isEmpty()) {
			String op = o.pop();
			int v2 = v.pop();
			int v1 = v.pop();
			int r = eval(v1, v2, op);
			v.push(r);
		}

		int r = v.pop();
		return r;
	}

	public static int cal2(String[] a) {
		Stack<Integer> n = new Stack<Integer>();
		Stack<String> o = new Stack<String>();
		int r = 0;
		for (int i = 0; i < a.length; i++) {
			String e = a[i];
			if (e.equals("(")) {

			} else if (e.matches("[0-9]+")) {
				n.push(Integer.parseInt(e));
			} else if (e.matches("\\+|-|\\*|/")) {
				o.push(e);
			} else if (e.equals(")")) {
				int n1 = n.pop();
				int n2 = n.pop();
				String op = o.pop();
				int res = eval(n1, n2, op);
				n.push(res);
			}
		}
		if (!o.isEmpty()) {
			int n1 = n.pop();
			int n2 = n.pop();
			String op = o.pop();
			r = eval(n1, n2, op);
		} else {
			r = n.pop();
		}
		return r;
	}

	public static int eval(int a, int b, String o) {
		int r = 0;
		if (o.equals("+")) {
			r = a + b;
		}
		if (o.equals("-")) {
			r = a - b;
		}
		if (o.equals("*")) {
			r = a * b;
		}
		if (o.equals("/")) {
			r = a / b;
		}
		return r;
	}

	public static void main(String[] args) {
//		String[] a = { "(", "1", "+", "(", "(", "2", "+", "3", ")", "*", "(", "4", "*", "5", ")", ")", ")" };
		String[] a= {"3", "+", "5", "*", "6", "-", "7", "*", "(", "8","+", "5", ")"};
		int r = cal(a);
		System.out.println(r);
		// System.out.println("t".matches("\\+|-|\\*|/"));
	}

}
